UVa/10080 - Gopher II/10080.cpp

   1 /*
   2   Problem: Gopher II
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Algorithm: Maximum bipartite matching, using Ford-Fulkerson method.
   7  */
   8
   9 using namespace std;
  10 #include <algorithm>
  11 #include <iostream>
  12 #include <iterator>
  13 #include <sstream>
  14 #include <fstream>
  15 #include <cassert>
  16 #include <climits>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <string>
  20 #include <cstdio>
  21 #include <vector>
  22 #include <cmath>
  23 #include <queue>
  24 #include <deque>
  25 #include <stack>
  26 #include <map>
  27 #include <set>
  28
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 struct point{
  32   double x, y;
  33 };
  34
  35 double d(const point &a, const point &b){
  36   return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
  37 }
  38
  39 int cap[202][202];
  40 int prev[202];
  41
  42 int fordFulkerson(int n, int s, int t){
  43   int ans = 0;
  44   while (true){
  45     fill(prev, prev+n, -1);
  46     queue<int> q;
  47     q.push(s);
  48     while (q.size() && prev[t] == -1){
  49       int u = q.front();
  50       q.pop();
  51       for (int v=0; v<n; ++v){
  52         if (v != s && prev[v] == -1 && cap[u][v] > 0)
  53           prev[v] = u, q.push(v);
  54       }
  55     }
  56
  57     if (prev[t] == -1) break;
  58
  59     int bottleneck = INT_MAX;
  60     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  61       bottleneck = min(bottleneck, cap[u][v]);
  62     }
  63     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  64       cap[u][v] -= bottleneck;
  65       cap[v][u] += bottleneck;
  66     }
  67     ans += bottleneck;
  68   }
  69   return ans;
  70 }
  71
  72
  73
  74 int main(){
  75   int n, m, s, v;
  76   while (scanf("%d %d %d %d", &n, &m, &s, &v) == 4){
  77     vector<point> gophers(n);
  78     vector<point> holes(m);
  79
  80     for (int i=0; i<n; ++i) scanf("%lf %lf", &gophers[i].x, &gophers[i].y);
  81     for (int i=0; i<m; ++i) scanf("%lf %lf", &holes[i].x, &holes[i].y);
  82
  83     memset(cap, 0, sizeof cap);
  84     const int source = n + m, sink = n + m + 1;
  85
  86     for (int i=0; i<n; ++i){
  87       for (int j=0; j<m; ++j){
  88         if (d(gophers[i], holes[j]) <= s*v - 1e-9){
  89           cap[i][n+j] = 1;
  90         }
  91       }
  92     }
  93
  94     for (int i=0; i<n; ++i) cap[source][i] = 1;
  95     for (int j=0; j<m; ++j) cap[n+j][sink] = 1;
  96
  97
  98     int lucky = fordFulkerson(n + m + 2, source, sink);
  99
 100     printf("%d\n", n - lucky);
 101   }
 102   return 0;
 103 }